#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:
    def maxInWindows(self, nums, size):
        # if not nums or not size:
        #     return []
        if size == 0 or len(nums) < size:
            return []

        self.queue = []
        self.nums = nums
        self.size = size

        self.results = []
        self.init_queue()

        for idx in range(size, len(nums)):
            # print('slide idx', idx)
            self.slide(idx)

        return self.results

    def init_queue(self):
        heads = self.nums[:self.size]
        # print(heads)

        max_value = heads[0]
        max_idx   = 0

        for idx, v in enumerate(heads[1:], 1):
            if v >= max_value:
                # print(idx, v)
                max_value = v
                max_idx = idx

        # for idx in range(max_idx, len(heads)):
        #     self.queue.push(idx)
        self.queue = list(range(max_idx, len(heads)))
        self.results.append(max_value)
        # print('m', max_idx, max_value)
        # print(self.queue)

    def slide(self, slide_in_nums_idx):
        v = self.nums[slide_in_nums_idx]

        assert slide_in_nums_idx - self.queue[0] <= self.size

        # slide out
        if slide_in_nums_idx - self.queue[0] == self.size:
            self.queue.pop(0)

        # optimize minum
        truncate_idx = len(self.queue)
        # print('t a', truncate_idx)
        for queue_idx, nums_idx in enumerate(self.queue):
            left_num = self.nums[nums_idx]
            # print('left ', left_num, v)
            if v >= left_num:
                truncate_idx = queue_idx
                break

        # print('t', truncate_idx)
        self.queue = self.queue[:truncate_idx]
        # print(self.queue)
        self.queue.append(slide_in_nums_idx)

        self.results.append(self.nums[ self.queue[0] ])

        # print(self.queue)


def test():
    s = Solution()
    # r = s.maxInWindows([1, 2, 10, 3, 20, 5], 4)
    # print(r)
    r = s.maxInWindows([2, 3, 4, 2, 6, 2, 5, 1], 3)
    print(r)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
